package games;

import java.util.Iterator;

import minmax.GameMove;
import minmax.GameOutcome;
import minmax.GameState;

/**
 * is a model for tic-tac-toe game
 */
public class TicTacToeState implements GameState<TicTacToeState.TicTacToeMove> {

	/**
	 * determines a player who is going to make the next move
	 */
	private boolean player;
	
	/**
	 * describes playing board: two bits describe each cell
	 */
	private int board;
	
	/**
	 * cached game result, if any
	 */
	private GameOutcome outcome;
	
	/**
	 * describes number of pieces on each diagonal (2 bits * 2 players * 8 diagonals)
	 */
	private int diagonals;
	
	/**
	 * list of performed moves
	 */
	private TicTacToeMove[] moves;
	
	/**
	 * number of performed moves
	 */
	private int size;
	
	/**
	 * counts number of pieces that each player has on each diagonal
	 * and stores the result, making it cached. 
	 * 
	 * @param player is the piece owner
	 * @param diagonal is in [0..7[ - number of diagonal
	 * @param inc tells whether piece is put or withdrawn
	 * @return new pieces count on this diagonal for the player
	 */
	private int update(boolean player, int diagonal, boolean inc) {
		assert 0 <= diagonal && diagonal < 8;
		int offset = player ? 2 * diagonal + 16 : 2 * diagonal;
		int mask = 3 << offset;
		// read
		int count = (diagonals & mask) >>> offset;
		// modify
		count += inc ? 1 : -1;
		assert 0 <= count && count <= 3;
		// write
		diagonals = (diagonals & ~mask) | (count << offset);
		return count;
	}
	
	/**
	 * updates cached diagonals counters according to a step
	 * made/withdrawn
	 * 
	 * @param step is move object
	 * @param inc determines between a new and withdrawn move
	 * @return whether a game result is modified
	 */
	private boolean update(TicTacToeMove step, boolean inc) {
		int bound = inc ? 3 : 2;
		boolean player = step.player();
		boolean modified = false;
		modified |= update(player, step.i, inc) == bound;
		modified |= update(player, step.j + 3, inc) == bound;
		if (step.i == step.j) {
			modified |= update(player, 6, inc) == bound;
		}
		if (step.i == 2 - step.j) {
			modified |= update(player, 7, inc) == bound;
		}
		return modified;
	}
	
	/**
	 * creates a fresh game, player <code>false</code> is going to make a move
	 */
	public TicTacToeState() {
		moves = new TicTacToeMove[9];
	}
	
	@Override
	public void move(TicTacToeMove step) {
		// validate the move
		if (outcome != null || player != step.player() || (board & step.cellMask) != 0) {
			throw new IllegalArgumentException("Invalid move: " + step);
		}
		// apply the move
		player = !player;
		board |= step.moveMask;
		moves[size] = step;
		size++;
		// update cached values
		if (update(step, true)) {
			outcome = GameOutcome.resolve(step.player());
		} else if (size == 9) {
			outcome = GameOutcome.Draw;
		}
	}

	@Override
	public void backtrack() {
		if (size == 0) {
			throw new IllegalStateException("Not a single move have been performed yet");
		}
		// withdraw the move
		player = !player;
		size--;
		board &= (~moves[size].cellMask);
		// update cached values
		update(moves[size], false);
		outcome = null;
	}

	@Override
	public Iterator<TicTacToeMove> moves() {
		if (outcome != null) {
			throw new IllegalStateException("Game is finished, no further moves are possible");
		}
		return new MoveIterator(player, board);
	}

	@Override
	public boolean canMove(TicTacToeMove move) {
		return cell(move.i, move.j) == null;
	}

	@Override
	public boolean player() {
		return player;
	}

	@Override
	public int evaluate(boolean maximize) {
		if (outcome == null || outcome == GameOutcome.Draw) {
			return 0;
		} else {
			boolean player = maximize ? this.player : !this.player;
			boolean winner = outcome.player();
			return player == winner ? 1 : -1;
		}
	}

	@Override
	public boolean isFinished() {
		return outcome != null;
	}
	
	@Override
	public GameOutcome outcome() {
		if (outcome == null) {
			throw new IllegalStateException("Game is not finished");
		}
		return outcome;
	}

	public TicTacToeState clone() {
		TicTacToeState copy;
		try {
			copy = (TicTacToeState) super.clone();
			copy.moves = copy.moves.clone();
		} catch (CloneNotSupportedException e) {
			throw new AssertionError("clone failed");
		}
		return copy;
	}
	
	/**
	 * state is fully determined by a sequence of moves
	 * 
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode() {
		int result = 0;
		for (int i = 0; i < size; i++) {
			result = 31 * result + moves[i].hashCode();
		}
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj == null || !(obj instanceof TicTacToeState)) {
			return false;
		}
		TicTacToeState other = (TicTacToeState) obj;
		boolean result = this.size == other.size && this.board == other.board;
		for (int i = 0; i < this.size && result; i++) {
			result = this.moves[i] == other.moves[i];
		}
		return result;
	}

	/**
	 * examines a given cell
	 * 
	 * @param i is in 0 .. 2
	 * @param j is in 0 .. 2
	 * @return <code>null</code> is cell is empty and the corresponding
	 *  player otherwise
	 */
	public Boolean cell(int i, int j) {
		if (i < 0 || j < 0 || i > 2 || j > 2) {
			throw new IllegalArgumentException("invalid cell : (" + i + ", " + j + ")" );
		}
		int cell = (board >> (2 * (3 * i + j))) & 3;
		return cell == 0 ? null : (cell & 1) == 0;
	}
	
	/**
	 * describes a game move
	 */
	public static final class TicTacToeMove implements GameMove {

		/**
		 * all move instances are cached
		 */
		private static TicTacToeMove[][] MOVES;
		
		static {
			MOVES = new TicTacToeMove[2][];
			MOVES[0] = new TicTacToeMove[9];
			MOVES[1] = new TicTacToeMove[9];
			for (int i = 0; i < 9; i++) {
				MOVES[0][i] = new TicTacToeMove(false, i);
				MOVES[1][i] = new TicTacToeMove(true, i);
			}
		}
		
		/**
		 * player that takes the move
		 */
		private boolean player;
		
		/**
		 * board cell affected
		 */
		public final int cell;
		
		/**
		 * row of the cell
		 */
		public final int i;
		
		/**
		 * column of the cell
		 */
		public final int j;
		
		/**
		 * binary mask to make the move
		 */
		public final int moveMask;
		
		/**
		 * binary mask to access the entire cell
		 */
		public final int cellMask;
		
		/**
		 * creates move instance
		 * 
		 * @param player is the player
		 * @param cell is the cell
		 */
		private TicTacToeMove(boolean player, int cell) {
			assert 0 <= cell && cell < 9;
			this.player = player;
			this.cell = cell;
			i = cell / 3;
			j = cell % 3;
			moveMask = 1 << ((cell * 2) + (player ? 1 : 0));
			cellMask = 3 << (cell * 2);
		}
		
		@Override
		public boolean player() {
			return player;
		}
		
		/**
		 * locates corresponding move instance
		 * 
		 * @param player is the player
		 * @param cell is the cell
		 * @return instance
		 */
		public static TicTacToeMove valueOf(boolean player, int cell) {
			assert 0 <= cell && cell < 9;
			return MOVES[player ? 1 : 0][cell];
		}
		
	}
	
	/**
	 * goes through a set of available moves, it takes only a single integer to store
	 * the state of iterator
	 */
	private static class MoveIterator implements Iterator<TicTacToeState.TicTacToeMove> {

		/**
		 * state of iterator
		 */
		private int data;
		
		/**
		 * create iterator
		 * 
		 * @param player is the player
		 * @param board is current board state
		 */
		public MoveIterator(boolean player, int board) {
			// bits: 25..16 (1 means a cell is free), 7 (1 means player is true), 3..0 - cursor
			// set free cells
			int rpin = 3, wpin = 1 << 16;
			for (int i = 0; i < 9; i++) {
				if ((board & rpin) == 0) {
					data |= wpin;
				}
				rpin <<= 2;
				wpin <<= 1;
			} 
			// set player
			if (player) {
				data |= (1 << 7);
			}
		}
		
		@Override
		public boolean hasNext() {
			return (data >> 8) != 0;
		}

		@Override
		public TicTacToeMove next() {
			if (!hasNext()) {
				throw new IllegalStateException("Iterator is empty");
			}
			int position = (data & 15);
			int pin = (1 << 16) << position;
			// there must be a free cell
			while ((data & pin) == 0) {
				position++;
				pin <<= 1;
				data++;
			}
			// erase the used cell
			data &= (~pin);
			data++;
			return TicTacToeMove.valueOf((1 & (data >> 7)) == 1, position);
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException("read-only iterator");
		}
	};
	
}
